package com.lwx.leetcode.dp;

/**
 * 最长回文串
 */
public class Top5 {
    public static void main(String[] args) {
        Top5 o = new Top5();
        String s = "babad";
        String ret = o.longestPalindrome(s);
        System.out.println(ret);
    }

    public String longestPalindrome(String s) {
        String ret = null;

        if (s == null || s.length() == 0) {
            return null;
        }

        int maxLen = 1;
        //dp[i][j] s[i...j]是否为回文串
        boolean[][] dp = new boolean[s.length()][s.length()];
        //只有一个字符的串为回文串
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
        }
//        ret = s.substring(0,1);

        //字符串长度为1
        if (s.length() == 1) {
            maxLen = 1;
            ret = s;
            return ret;
        }
        //L代表数组长度
        for (int L = 2; L <= s.length(); L++) {
            //数组起始下标 i
            for (int i = 0; i < s.length(); i++) {
                //数组结束下标 j
                int j = i + L - 1;
                if (j >= 0 && j < s.length()) {
                    boolean eqPartFlag = s.charAt(i) == s.charAt(j);
                    if (L == 2 && eqPartFlag) {
                        dp[i][j] = true;
                    } else if (eqPartFlag) {
                        dp[i][j] = dp[i + 1][j - 1];
                    } else {
                        dp[i][j] = false;
                    }

                    if (L > maxLen && dp[i][j]) {
                        maxLen = L;
                        ret = s.substring(i, j);
                    }
                }
            }
        }
        return ret;
    }
}
